package interview.binarysearch;

public class BinarySearch {
	// Assume array is sorted in ascending order
	public int search(int[] array, int target, boolean recursive) {
		if(recursive) {
			return binarySearchRecursive(array, 0, array.length - 1, target);
		} else {
			return binarySearchIterative(array, target);
		}
		
	}

	private int binarySearchIterative(int[] array, int target) {
		int left, right;
		left = 0;
		right = array.length - 1;
		int mid;
		while(left < right) {
			mid = left + (right - left) / 2;
			if(target == array[mid]) {
				return mid;
			}
			if(target > array[mid]) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return -1;
	}

	private int binarySearchRecursive(int[] array, int left, int right, int target) {
		if(left > right)
			return -1;
		
		int mid = left + (right - left) / 2;
		if(target == array[mid]) {
			return mid;
		}
			
		if(target > array[mid]) {
			left = mid + 1;
			return binarySearchRecursive(array, left, right, target);
		} else {
			right = mid - 1;
			return binarySearchRecursive(array, left, right, target);
		}
	}
}
